class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        set<string>hash(bank.begin(),bank.end());
        set<string>vis;
        string change="ATGC";
        if(startGene==endGene)return 0;
        if(!hash.count(endGene))return -1;
        queue<string>q;
        q.push(startGene);
        vis.insert(startGene);
        int step=0;
        while(q.size())
        {
            step++;
            int ret=q.size();
            while(ret--)
            {
                string t=q.front();
                q.pop();
                for(int i=0;i<8;i++)
                {
                    string tmp=t;
                    for(int j=0;j<4;j++)
                    {
                        tmp[i]=change[j];
                        if(hash.count(tmp)&&!vis.count(tmp))
                        {
                            if(tmp==endGene)return step;
                            q.push(tmp);
                            vis.insert(tmp);
                        }
                    }
                }
            }     
            
        }
        return -1;
    }
};
